Breadth-first search (BFS)

Breadth-first search (BFS) is a widely used algorithm for traversing or searching tree and graph data structures. It starts at a selected node (often referred to as the 'root' in the context of trees), and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. This characteristic allows BFS to provide the shortest path to a target node in an unweighted graph, which is one of its most significant advantages.

Algorithm Workflow

1. Initialization: BFS begins by marking the initial node as visited and then inserting it into a queue.
2. Exploration: While the queue is not empty, the process continues:
   • The node at the front of the queue is dequeued.
   • Each adjacent node is inspected. If it has not been visited, it is marked as visited and then added to the queue.

Complexity

• Worst-case time complexity: $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges in the graph.
• Worst-case space complexity: $O(V)$, which occurs when all vertices are held in the queue.
• Optimality: BFS is optimal for finding the shortest path in an unweighted graph.

Implementation

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')  # Process the vertex as needed
            # Enqueue all adjacent vertices that have not been visited
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

Practical Applications

BFS is used in a variety of applications due to its robustness and simplicity:

• Shortest Path Problems: Finding the shortest path on unweighted graphs.
• Connectivity Tests in Networks: Checking if there is a path between two nodes.
• Crawlers in Search Engines: BFS is used by web crawlers of search engines to visit web pages and collect data.
• Social Networking Applications: In platforms like Facebook, BFS can help find the shortest path between users, which can be interpreted as degrees of separation between users.

BFS vs. DFS

While both BFS and depth-first search (DFS) are fundamental for searching graphs, they have different properties:

• Memory Usage: BFS generally requires more memory than DFS because it stores all children of all nodes at a given depth before moving deeper.
• Path Finding: BFS is generally preferred for path finding on unweighted graphs because it always provides the shortest path.